#define _CRT_SECURE_NO_WARNINGS 1

#include"SList.h"

void SListPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void SListPushBack(SLNode** pphead, SLNDataType x)
{
	SLNode* NewNode = CreateNewNode(x);

	if (*pphead == NULL)
	{
		*pphead = NewNode;
	}
	else
	{
		SLNode* tail = *pphead;//tail 尾巴
		while (tail->next != NULL)//找到尾节点
		{
			tail = tail->next;
		}
		tail->next = NewNode;
	}
}

SLNode* CreateNewNode(SLNDataType x)
{
	SLNode* NewNode = (SLNode*)malloc(sizeof(SLNode));
	if (NewNode == NULL)
	{
		printf("malloc failed!\n");
		exit(-1);
	}
	NewNode->data = x;
	NewNode->next = NULL;
	return NewNode;
}

void SListPushFront(SLNode** pphead, SLNDataType x)
{
	SLNode* NewNode = CreateNewNode(x);

	NewNode->next = *pphead;
	*pphead = NewNode;
}

void SListPopBack(SLNode** pphead)
{
	assert(*pphead != NULL);
	if ((*pphead)->next == NULL)//如果只有一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

void SListPopFront(SLNode** pphead)
{
	assert(*pphead != NULL);
	SLNode* begin = *pphead;
	*pphead = (*pphead)->next;
	free(begin);
	begin = NULL;
}

SLNode* SListFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

void SListInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	SLNode* NewNode = CreateNewNode(x);
	if (*pphead == pos)
	{
		NewNode->next = *pphead;
		*pphead = NewNode;
	}
	else
	{
		SLNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		posPrev->next = NewNode;
		NewNode->next = pos;
	}
}

void SListInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos != NULL);
	SLNode* NewNode = CreateNewNode(x);
	NewNode->next = pos->next;
	pos->next = NewNode;
	//和前面对比，单链表的缺陷是要找pos的前一个要从头往后找
}

void SListEarse(SLNode** pphead, SLNode* pos)
{
	assert(*pphead != NULL);
	assert(pos != NULL);
	if (*pphead == pos)//如果是头删
	{
		*pphead = pos->next;
		free(pos);
		pos = NULL;
	}
	else
	{
		SLNode* posPrev = *pphead;
		while (posPrev->next != pos)
		{
			posPrev = posPrev->next;
		}
		posPrev->next = pos->next;
		free(pos);
		pos = NULL;//可以不写，形参不会改变实参，这个野指针会被栈帧销毁，但是个好习惯emm
	}
}

void SListEarseAfter(SLNode* pos)
{
	//1 2 3 4
	assert(pos != NULL);
	assert(pos->next != NULL);
	SLNode* posAfter= pos->next;
	pos->next = posAfter->next;
	free(posAfter);
	posAfter = NULL;//可以不写，形参不会改变实参，这个野指针会被栈帧销毁
}

void SListDestroy(SLNode** pphead)
{
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

SLNode* SListMerge(SLNode* pLista, SLNode* pListb)//合并两个链表(归并的思想)
{
	if (pLista == NULL)
	{
		return pListb;
	}
	if (pListb == NULL)
	{
		return pLista;
	}

	SLNode* cur = NULL;//先创建前驱指针指向两个链表中第一个元素小的值
	if (pLista->data <= pListb->data)
	{
		cur = pLista;
		pLista = pLista->next;
	}
	else
	{
		cur = pListb;
		pListb = pListb->next;
	}

	SLNode* pListc = cur;//记录要返回的头节点
	while (pLista && pListb)//不为空就让两链表中元素小的尾插到新链表
	{
		if (pLista->data <= pListb->data)
		{
			cur->next = pLista;
			cur = pLista;
			pLista = pLista->next;
		}
		else
		{
			cur->next = pListb;
			cur = pListb;
			pListb = pListb->next;
		}
	}

	if (pLista == NULL)//如果其中一个为空，直接指向另一个链表
	{
		cur->next = pListb;
	}
	else
	{
		cur->next = pLista;
	}
	return pListc;
}